package main.java.indi.zyj.c150.recursion;

public class _01_basics {

    public static void main(String[] args) {
        System.out.println(Factorial(5));
        System.out.println(reverse("abcde", 4));
    }


    static int Factorial(int n){
        if (n == 1){
            return 1;
        }
        return n * Factorial(n - 1);
    }

    /**
     * 对arr的所有元素求和
     * 找重复：
     * 找变化：变化的量应该作为参数
     * 找边界：出口
     * @param arr
     */
    static int f3(int[] arr, int begin) {
        if (begin == arr.length - 1) {
            return arr[begin];
        }
        return arr[begin] + f3(arr, begin + 1);
    }

    /**
     * 翻转字符串
     * @param src
     * @param end
     * @return
     */
    static String reverse(String src, int end) {
        if (end == 0){
            return src.charAt(0) + "";
        }
        return src.charAt(end) + reverse(src, end - 1);
    }


    /**
     * O(2^n)
     * @param n
     * @return
     */
    static int fib(int n) {
        if (n == 1 || n == 2)
            return 1;
        return fib(n - 1) + fib(n - 2);
    }

    /**
     *      最大公约数
     * @param m
     * @param n
     * @return int
     */
    static int gcd(int m, int n) {
        if (n == 0)
            return m;
        return gcd(n, m % n);
    }

    static void insertSort(int[] arr, int k) {

        if (k == 0){
            return ;
        }

        insertSort(arr, k - 1);

        int x = arr[k];
        int index = k - 1;
        while (index > -1 && arr[index] > x){
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = x;

    }


}
